COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%search[e89,jmc]		Notes on Search
C00004 ENDMK
C⊗;
%search[e89,jmc]		Notes on Search

1. Search spaces are enormously reduced by equivalence relations
appropriate to achieving subgoals.  In the 15 puzzle (or in the
n↑2-1 puzzle generally), it is never necessary to consider the
positions of more than two tiles and the blank, and usually
only one tile plus blank.  This means the space never has
more than 16.15.14 < 16↑3 = 4096 distinguishable positions.

2. Consider ((1 2 3 b)(x x x y) u v) where y ≠ 4.  We can't
improve this situation without giving up the (1 2 3 .) configuration.
We can discover this by working backward from the goal of getting
4 in place.  In fact, if we preserve (1 2 3 .), all we can
do is move  y  in and out of position 4.  It is probably beyond
the scope of our present investigation to make a program that
can learn this.  What does it require?

3. Let 

(declare reduced-positions 
	 (classes positions
		  (lambda (pos1 pos2) 
			  (and (equal (loc m pos1) (loc m pos2))
			       (equal (loc (1+ m) pos1) (loc (1+ m) pos2))
			       (equal (loc blank pos1) (loc blank pos2))))))